package 中等.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X",
 * 白棋记作字母 "O"，空余位置记作 "."。当落下的棋子与其
 * 他相同颜色的棋子在行、列或对角线完全包围（中间不存在
 * 空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。
 * 「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形
 * 成可翻转棋子的棋盘残局，其状态记作 chessboard。若下
 * 一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。
 * 注意：
 * 若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋
 * 输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fHi6rV
 */
public class 黑白翻转棋_lcp41 {

    public static void main(String[] args) {

        黑白翻转棋_lcp41 impl = new 黑白翻转棋_lcp41();
        System.out.println(impl.flipChess(new String[]{
                ".O.....",
                ".O.....",
                "XOO.OOX",
                ".OO.OO.",
                ".XO.OX.",
                "..X.X.."
        }));

    }

    /**
     * 广度优先搜索
     * 数据量较小，可以枚举每一个空余位置变成黑棋，搜索其行
     * ，列，对角线某一个方向开始是白棋结束是黑棋的所有白棋
     * 将其变为黑棋放入队列中
     */
    public int flipChess(String[] chessboard) {
        int ans = 0;

        for (int i = 0; i < chessboard.length; i++) {
            for (int j = 0; j < chessboard[0].length(); j++) {
                if (chessboard[i].charAt(j) == '.') {
                    ans = Math.max(ans, bfs(i, j, chessboard));
                }
            }
        }

        return ans;
    }

    private int bfs(int i, int j, String[] chessboard) {
        int ans = 0;
        boolean[][] visited = new boolean[chessboard.length][chessboard[0].length()];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{i, j});
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] cur = queue.pollFirst();
                for (int di = -1; di <= 1; di++) {
                    for (int dj = -1; dj <= 1; dj++) {
                        if (di == 0 && dj == 0) continue;
                        List<int[]> list = flip(cur[0], cur[1], di, dj, chessboard);
                        for (int[] n : list) {
                            if (!visited[n[0]][n[1]]) {
                                queue.add(n);
                                visited[n[0]][n[1]] = true;
                                ans++;
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }

    // 找到某个方向以 O...X 结尾的所有 O 的位置集合
    private List<int[]> flip(int i, int j, int di, int dj, String[] chessboard) {
        List<int[]> list = new ArrayList<>();
        i += di;
        j += dj;

        while (i >= 0 && i < chessboard.length &&
                j >= 0 && j < chessboard[0].length()) {
            char c = chessboard[i].charAt(j);
            if (c == '.') {
                return new ArrayList<>();
            } else if (c == 'O') {
                list.add(new int[]{i, j});
            } else {
                return list;
            }
            i += di;
            j += dj;
        }

        // 注意：必须以 X 结束
        return new ArrayList<>();
    }

}
